'''
https://leetcode.cn/problems/fibonacci-number/description/
'''
import time
from functools import cache

import numpy as np


class Solution:
    A = np.array([
        [1, 1],
        [1, 0]
    ])
    lambda1, lambda2 = (1 + np.sqrt(5)) / 2, (1 - np.sqrt(5)) / 2
    Λ = np.array([
        [lambda1, 0],
        [0, lambda2]
    ])
    X = np.array([
        [lambda1, lambda2],
        [1, 1]
    ])
    X_inv = np.linalg.inv(X)
    f_0 = np.array([1, 0])
    # 模拟
    def fib(self, n: int) -> int:
        def f(n):
            if n == 0:
                return 0
            if n == 1:
                return 1
            return f(n - 1) + f(n - 2)
        @cache
        def f2(n:int) -> int:
            if n == 0:
                return 0
            if n == 1:
                return 1
            return f(n - 1) + f(n - 2)

        return f2(n)

    # 基础dp
    def fib2(self, n: int) -> int:
        if n < 2: return n
        dp = [0] * (n + 1)
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

    # 省空间dp
    def fib3(self, n: int) -> int:
        if n < 2: return n
        a, b = 0, 1
        for i in range(2, n + 1):
            a, b = b, a + b
        return b

    # 特征值分解，矩阵快速幂
    def fib4(self, n: int) -> int:
        if n < 2: return n
        # f_n = (AA...A).dot(x_0)   = (X ΛΛ...Λ X逆 ).dot(f_0) = (X(Λ^n)X逆).dot(f_0)
        f_n = Solution.X.dot(Solution.Λ ** n).dot(Solution.X_inv).dot(Solution.f_0)
        # print(f_n)
        return int(round(f_n[1]))

s = Solution()
for n in range(10000):
    s1 = time.time() * 1000
    r1 = s.fib(n)
    s2 = time.time() * 1000
    r2 = s.fib2(n)
    s3 = time.time() * 1000
    r3 = s.fib3(n)
    s4 = time.time() * 1000
    r4 = s.fib4(n)
    s5 = time.time() * 1000
    # ans = r1 == r2 == r3 == r4
    ans = r2 == r3 == r4
    print(f"n:{n}, 是否正确:{ans}, 记忆化搜索耗时: {s2-s1:5f}ms, dp耗时：{s3-s2:5f}, 滚筒dp:{s4-s3:5f}ms, 特征值分解快速幂耗时：dp:{s5-s4:5f}ms.")
    # print(f"n:{n}, 是否正确:{ans}, ans:{r4}, dp耗时：{s3-s2:5f}, 滚筒dp:{s4-s3:5f}ms, 特征值分解快速幂耗时：dp:{s5-s4:5f}ms.")

